package LeetCode;


/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}18:18
 */
public class LeetCode98 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public boolean isValidBST(TreeNode root) {
        if (root == null){
            return true;
        }
        return isLeft(root.left,root.val) && isRight(root.right,root.val);
    }
    public boolean isLeft(TreeNode root,int val){
        if (root == null){
            return true;
        }
        if (root.val >= val){
            return false;
        }else {
            return isLeft(root.left,root.val) && isRight(root.right,root.val);
        }
    }
    public boolean isRight(TreeNode root,int val){
        if (root == null){
            return true;
        }
        if (root.val <= val){
            return false;
        }else {
            return isLeft(root.left,root.val) && isRight(root.right,root.val);
        }
    }

    // 中序遍历牛批 中序遍历先访问左子结点 之后访问父节点之后访问右子节点 访问的这三个节点大小都是从小到大的只要将前一个存起来 与下一个遍历节点进行比较就行了
    long pre = Long.MIN_VALUE;
    public boolean isValidBST2(TreeNode root) {
        if (root == null) {
            return true;
        }
//        // 访问左子树
//        if (!isValidBST2(root.left)) {
//            return false;
//        }
//        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
//        if (root.val <= pre) {
//            return false;
//        }
//        pre = root.val; // 太妙了
//        // 访问右子树
//        return isValidBST2(root.right);
        if (!isValidBST(root.left)){
            return false;
        }
        if (root.val <= pre){
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(2);
        node.left = new TreeNode(1);
        node.right = new TreeNode(3);
//        node.left = new TreeNode(1);
//        node.right = new TreeNode(4);
//        node.right.left = new TreeNode(3);
//        node.right.right = new TreeNode(6);
        System.out.println(new LeetCode98().isValidBST2(node));
    }
}
